Khi tiến hành xâm chiếm Nam kỳ, người Pháp tổ chức hệ thống cai trị qua hai giai đoạn. Trong giai đoạn đầu, từ 1861 đến 1879, người Pháp thành lập Soái phủ Nam kỳ (Gouvernement des Amiraux) do các đô đốc của Hải quân Pháp đứng đầu, trông coi việc cai trị hành chính và binh bị. Bắt đầu năm 1879, người Pháp đặt chức vụ Thống đốc Nam Kỳ (Gouverneur-général de la Cochinchine) để cai trị mảnh đất thuộc địa này. Chức vụ thống đốc này trực thuộc bộ Thuộc địa và bộ Hải quân Pháp. Sau khi áp đặt chế độ bảo hộ, người Pháp đặt thêm chức vụ Khâm sứ Trung Kỳ (Résident supérieur d'Annam) và Thống sứ Bắc Kỳ (Résident supérieur du Tonkin). Hai người này trực thuộc bộ Ngoại giao Pháp.[3]

Ngày 17 tháng 10 năm 1887, viên Tổng thống Pháp ký sắc lệnh thành lập Phủ Toàn quyền Đông Dương, còn gọi là Phủ Toàn quyền Đông Pháp (Gouvernement général de l'Indochine Française). Toàn quyền Đông Pháp là người có quyền hành cao nhất trong thể chế chính trị Pháp trên toàn cõi Bắc kỳ, Nam kỳ và Cao Miên. Riêng nước Đại Nam (phần đất Trung kỳ còn lại, đang chịu sự bảo hộ của thực dân Pháp) thì Hoàng đế nhà Nguyễn vẫn là người có quyền tối thượng, tất nhiên là trên danh nghĩa. Đứng đầu cả ba kỳ là: Thống đốc Nam kỳ (có sách gọi Thủ hiến), Khâm sứ Trung kỳ (có sách gọi Đại Trú sứ) và Thống sứ Bắc kỳ (có sách gọi Tổng Trú sứ), cả ba đều nằm dưới quyền giám sát và điều khiển tối cao của viên Toàn quyền Đông Pháp, trực thuộc bộ Thuộc địa. Đến năm 1900 quyền kiểm soát của Toàn quyền Đông Pháp được mở rộng thêm, bao gồm cả Ai Lao và Quảng Châu Loan.[4]